/*
 * @lc app=leetcode.cn id=673 lang=typescript
 *
 * [673] 最长递增子序列的个数
 */

// @lc code=start
function findNumberOfLIS(nums: number[]): number {
  const n = nums.length;
  // 以i字符为结尾最长递增子序列的长度
  const dp = new Array(n).fill(1);
  // 以i字符为结尾的最长递增子序列个数
  const cnt = new Array(n).fill(1);
  // 最长递增子序列的长度
  let max = 0;
  let ans = 0;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      // 在j后面形成更长的最长递增子序列
      if (nums[i] > nums[j]) {
        if (dp[j] + 1 > dp[i]) {
          dp[i] = dp[j] + 1;
          // 重置
          cnt[i] = cnt[j];
        } else if (dp[j] + 1 === dp[i]) {
          // 更新
          cnt[i] += cnt[j];
        }
      }
    }
    if (dp[i] > max) {
      // 重置
      max = dp[i];
      ans = cnt[i];
    } else if (dp[i] === max) {
      // 更新
      ans += cnt[i];
    }
  }

  return ans;
}
// @lc code=end
